/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * InternalNode.java
 * ---------------------------
 *
 */
package btree;

import static btree.BTree.DeletionReturn.ChildEvent.CHANGED_RIGHTMOST;
import static btree.BTree.DeletionReturn.ChildEvent.MERGE_LEFT;
import static btree.BTree.DeletionReturn.ChildEvent.MERGE_RIGHT;
import static btree.BTree.DeletionReturn.ChildEvent.NO_VALUECHG;
import static btree.BTree.DeletionReturn.ChildEvent.ROOT_COLLAPSE;
import static btree.BTree.DeletionReturn.ChildEvent.STOLE_LEFT;
import static btree.BTree.DeletionReturn.ChildEvent.STOLE_RIGHT;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import btree.BTree.AdditionReturn;
import btree.BTree.DeletionReturn;

/**
 * Represents the internal/root node of a b-tree.<br>
 * Generics proved, for this use, to be bulky and useless.
 */
@SuppressWarnings("unchecked")
public class InternalNode extends AbstractNode 
{
	protected NodeElement[] _elements;
	
	public InternalNode(
			NodeElement[] elems, int currentElems, AbstractNode rightPtr) 
	{
		_elements = elems.clone();
		_currentElems = currentElems;
		_rightPtr = rightPtr;
	}

	protected InternalNode(
			NodeElement elem, int order, AbstractNode rightPtr)
	{
		_elements = new NodeElement[order];
		_elements[0] = elem;
		_currentElems = 1;
		
		_rightPtr = rightPtr;
		
	}

	@Override
	public AdditionReturn add(
		RecElement inserting)
	{
		int ptrChangePos;
		AbstractNode addingNodePtr;
		
		if (inserting.compareTo(_elements[_currentElems - 1]) > 0) {
			ptrChangePos = POSITION_GREATEST;
			addingNodePtr = _rightPtr;
		}
		else {
			ptrChangePos = findPosition(inserting.value);
			if (ptrChangePos < 0) ptrChangePos = -(ptrChangePos + 1);
			addingNodePtr = _elements[ptrChangePos].nodePtr;
		}

		AdditionReturn splitHappens = addingNodePtr.add(inserting);

		if (splitHappens != null) {
			if (ptrChangePos == POSITION_GREATEST) _rightPtr = splitHappens.rightNode;
			else _elements[ptrChangePos].nodePtr = splitHappens.rightNode;
			
			splitHappens = addSameLevel(splitHappens.element);
		}

		return splitHappens;
	}

	@Override
	public long search(Comparable value) 
	{
		int pos = findPosition(value);
		
		if (pos == POSITION_GREATEST) {
			return _rightPtr.search(value);
		}
		else {
			if (pos < 0) pos = -(pos + 1);
			return _elements[pos].nodePtr.search(value);
		}
	}

	/* goes all the way to the left */
	@Override
	public Iterator<Long> orderedTraversal()
	{
		return _elements[0].nodePtr.orderedTraversal();
	}

	/**
	 * Same mechanism as LeafNode.addToLeaf(); differs only for the middle index.<br>
	 * To create a single method we should use reflection to instantiate the
	 * appropriate objects.
	 */
	private AdditionReturn addSameLevel(
			NodeElement inserting)
	{
		if (_currentElems < _elements.length) {
			orderedInsert(inserting);
			return null;
		}
		else {
			// buffer for all elements
			NodeElement[] tempElems = new NodeElement[_elements.length + 1];			
			System.arraycopy(_elements, 0, tempElems, 0, _elements.length);
			orderedInsertInArray(tempElems, _elements.length, inserting);
			
			/* similar but different from LeafNode */
			final int middleIdx = tempElems.length / 2;
			final int firstRightIdx = middleIdx + 1;

			// the new node won the custody of the children 
			NodeElement[] rightElems = new NodeElement[_elements.length];
			int rightCurrentElems = tempElems.length - firstRightIdx;
			System.arraycopy(tempElems, firstRightIdx, rightElems, 0, 
							 rightCurrentElems);
			AbstractNode rightRightPtr = _rightPtr;
			InternalNode newRightNode = new InternalNode(
					rightElems, rightCurrentElems, rightRightPtr);
			
			System.arraycopy(tempElems, 0, _elements, 0, middleIdx);
			Arrays.fill(_elements, middleIdx, _currentElems, null);				 
			_rightPtr = tempElems[middleIdx].nodePtr;
			_currentElems = middleIdx;

			// bubbling element. differently from leaf node, this is not kept
			// in the current node
			NodeElement splitHappens = new NodeElement(
					tempElems[middleIdx].value, this);
			return new AdditionReturn(splitHappens, newRightNode);
		}
	}
	
	@Override
	public DeletionReturn remove(
			Comparable value, AbstractNode leftSibling, AbstractNode rightSibling) 
	{
		/* Compute the position of the changing element, and its left/right 
		 * element pointers. */
		
		int valuePos = findPosition(value);
		
		AbstractNode leftChild, child, rightChild;
		
		if (valuePos == POSITION_GREATEST) {
			leftChild = _elements[_currentElems - 1].nodePtr;			
			child = _rightPtr;
			rightChild = null;
		}
		else {
			if (valuePos < 0) valuePos = -(valuePos + 1); // normalize

			if (valuePos == 0) leftChild = NULL_NODE;
			else leftChild = _elements[valuePos - 1].nodePtr;
			
			if (valuePos == _currentElems - 1) rightChild = _rightPtr;
			else rightChild = _elements[valuePos + 1].nodePtr;

			child = _elements[valuePos].nodePtr;
		}

		DeletionReturn bubbling = child.remove(value, leftChild, rightChild);
		if (bubbling == null) {
			return null;
		}
		else {
			return handleRemove(leftSibling, rightSibling, bubbling, valuePos);
		}
	}

	private DeletionReturn handleRemove(
			AbstractNode leftSibling, AbstractNode rightSibling, 
			DeletionReturn bubbling, int removalPos)
	{
		InternalNode leftInternal = (InternalNode)leftSibling;
		InternalNode rightInternal = (InternalNode)rightSibling;
		
		switch(bubbling.childEvent) {
		/* We don't need to change anything, because the rightmost val didn't change,
		 * so it's not contained in the current node */
		case NO_VALUECHG:
			return bubbling;

		/* The child node changed its rightmost value, so we must update 
		 * the current element.
		 * Watch out: we signal a CHANGED_RIGHTMOST only if the _rightPtr's
		 * child rightmost changed. */
		case CHANGED_RIGHTMOST:
			// must either be the righmost (->bubbles) or be in this node
			assert(removalPos >= 0 || removalPos == POSITION_GREATEST);
			
			if (removalPos != POSITION_GREATEST) {
				_elements[removalPos].value = bubbling.value;
				return new DeletionReturn(NO_VALUECHG, null);
			}
			else {
				return new DeletionReturn(CHANGED_RIGHTMOST, bubbling.value); 
			}

		/* The child node changed its rightmost value, so we must update 
		 * the current element. */
		case STOLE_RIGHT:
			assert(removalPos != POSITION_GREATEST);
			_elements[removalPos].value = bubbling.value;
			return new DeletionReturn(NO_VALUECHG, null);

		/* Both the child and its left sibling changed their rightmost,
		 * so we must update both. */
		case STOLE_LEFT:
			 // impossible for first element
			assert(removalPos > 0 || removalPos == POSITION_GREATEST);
			
			if (removalPos == POSITION_GREATEST) {
				_elements[_currentElems - 1].value = bubbling.leftNodeValue;
				return new DeletionReturn(CHANGED_RIGHTMOST, bubbling.value);
			}
			else {
				_elements[removalPos].value = bubbling.value;
				_elements[removalPos - 1].value = bubbling.leftNodeValue;
				return new DeletionReturn(NO_VALUECHG, null);
			}

		/* right sibling has the correct value, so we just set its pointer
		 * and delete the path element */ 
		case MERGE_RIGHT:
			assert(removalPos != POSITION_GREATEST);
			
			if (removalPos < _currentElems - 1) {
				_elements[removalPos + 1].nodePtr = _elements[removalPos].nodePtr;
				removeElement(removalPos);
			}
			else {
				_rightPtr = _elements[removalPos].nodePtr;
				removeElement(removalPos);
			}
			return operateAfterRemoval(leftInternal, rightInternal);

		/* we change the current element, and remove its left sibling.
		 * if the element is GREATEST, we only do the removal.<br>
		 * IMPORTANT NOTE: @see DeletionReturn.MERGE_LEFT */
		case MERGE_LEFT:
			assert(removalPos > 0 || removalPos == POSITION_GREATEST);

			if (removalPos == POSITION_GREATEST) {
				_rightPtr = _elements[_currentElems - 1].nodePtr;
				removeElement(_currentElems - 1);
			}
			else {
				_elements[removalPos].nodePtr = _elements[removalPos - 1].nodePtr;
				removeElement(removalPos - 1);
			}

			return operateAfterRemoval(leftInternal, rightInternal);

		default:
			throw new AssertionError(bubbling.childEvent);
		}
	}

	/** Do operations, if needed, after removal.<br>
	 * TODO: currently, for simplicity, always signals a CHANGED_RIGHTMOST;
	 * change to reflect real situation */
	private DeletionReturn operateAfterRemoval(
			InternalNode leftNode, InternalNode rightNode)
	{
		boolean isRoot = (leftNode == NULL_NODE && rightNode == NULL_NODE);
		if (isRoot) {
			if (_currentElems == 0) {
				return new DeletionReturn(ROOT_COLLAPSE, null);		
			}
			else {
				// no need to signal anything
				return new DeletionReturn(NO_VALUECHG, null);
			}
		}
		else {
			if (! hasMinimum()) {
				return interactWithSibling(leftNode, rightNode);
			}
			else {
				Comparable rightmostVal = getSubtreeRightmostVal();
				return new DeletionReturn(CHANGED_RIGHTMOST, rightmostVal);
			}
		}
	}
	
	/**
	 * Slightly different [non-abstractable] from InternalNode one because the latter
	 * need to know the equivalent value of the rightmost pointer.  
	 */
	private DeletionReturn interactWithSibling(
			AbstractNode remLeftPtr, AbstractNode remRightPtr)
	{
		/* First we try to steal to any one has min+1 */ 
		
		if (remRightPtr != null && remRightPtr.hasMinimumPlusOne()) {
			return stealRight(remRightPtr);
		}
	
		if (remLeftPtr != null && remLeftPtr.hasMinimumPlusOne()) {
			return stealLeft(remLeftPtr);
		}
		
		/* Then, if one is not present we merge with the other; otherwise
		 * we merge with the one with less elems */
		
		if (remLeftPtr == null) {
			return mergeRight(remRightPtr);
		}
		else if (remRightPtr == null) {
			return mergeLeft(remLeftPtr);
		}
		else { // if remLeftPtr != null && remRightPtr != null
			// merge with the one with less elems
			if (remLeftPtr._currentElems <= remRightPtr._currentElems) {
				return mergeLeft(remLeftPtr);
			}
			else {
				return mergeRight(remRightPtr);
			}
		}
	}

	private DeletionReturn stealRight(
			AbstractNode remRightPtr) 
	{
		NodeElement stolen = (NodeElement)remRightPtr.removeElement(0);
		
		NodeElement newRightmost = new NodeElement(
				getSubtreeRightmostVal(), _rightPtr);
		_rightPtr = stolen.nodePtr;
		fixedInsert(newRightmost, _currentElems);
		
		return new DeletionReturn(STOLE_RIGHT, getSubtreeRightmostVal());
	}
	
	private DeletionReturn stealLeft(
			AbstractNode remLeftPtr) 
	{
		InternalNode left = ((InternalNode)remLeftPtr);
		
		NodeElement newLeftmost = left.removeRightmost();
		fixedInsert(newLeftmost, 0);

		return new DeletionReturn(STOLE_LEFT, 
				getSubtreeRightmostVal(), 
				left.getSubtreeRightmostVal());
	}
	
	/** @see DeletionReturn.ChildEvent.MERGE_LEFT */
	private DeletionReturn mergeLeft(
			AbstractNode remLeftPtr)
	{
		InternalNode left = (InternalNode)remLeftPtr;

		// 1. for leaf nodes, we do have a leftNode.rightPtr in mezzo ai maroni			
		// 2. the retaining node is the left one
		NodeElement[] temp = new NodeElement[
			left._currentElems + _currentElems + 1];
		
		System.arraycopy(left._elements, 0, temp, 0, left._currentElems);
		temp[left._currentElems] = new NodeElement(
			left.getSubtreeRightmostVal(), left._rightPtr);
		System.arraycopy(_elements, 0, temp, left._currentElems + 1,
						 _currentElems);
		
		left._elements = temp;
		left._currentElems = left._currentElems + _currentElems + 1;
		left._rightPtr = _rightPtr;
		
		return new DeletionReturn(MERGE_LEFT, getSubtreeRightmostVal()); 
	}

	private DeletionReturn mergeRight(
			AbstractNode remRightPtr)
	{
		InternalNode right = (InternalNode)remRightPtr;

		// for leaf nodes, we do have a curreNode.rightPtr in mezzo ai maroni			
		NodeElement[] temp = new NodeElement[
			_currentElems + right._currentElems + 1];
		
		System.arraycopy(_elements, 0, temp, 0, _currentElems);
		temp[_currentElems] = new NodeElement(
			getSubtreeRightmostVal(), _rightPtr);
		System.arraycopy(right._elements, 0, temp, _currentElems + 1,
						 right._currentElems);
		
		_elements = temp;
		_currentElems = _currentElems + right._currentElems + 1;
		_rightPtr = right._rightPtr;
		
		return new DeletionReturn(MERGE_RIGHT, right.getSubtreeRightmostVal()); 
	}

	@Override
	protected Comparable getSubtreeRightmostVal()
	{
		return _rightPtr.getSubtreeRightmostVal();
	}

	@Override
	protected NodeElement[] getElementsPtr()
	{
		return _elements;
	}
	
	private NodeElement removeRightmost()
	{
		// create a full element from the rightPtr
		NodeElement newLeftmost = 
				new NodeElement(getSubtreeRightmostVal(), _rightPtr);
		
		// backup the rightmost ptr
		AbstractNode rightmostPtrCopy = _elements[_currentElems - 1].nodePtr;
		
		// delete the rightmost and replace the _rightPtr
		removeElement(_currentElems - 1);
		_rightPtr = rightmostPtrCopy;
		
		return newLeftmost;
	}
	
	////////////////////////////////////////////////////////////////////////////////
	// DEBUG METHODS 
	////////////////////////////////////////////////////////////////////////////////
	
	@Override
	public List<AbstractNode> getChildren()
	{
		List<AbstractNode> children = new ArrayList<AbstractNode>();
		
		for (NodeElement elem : _elements) {
			if (elem != null) children.add(elem.nodePtr);
			else break;
		}
		
		if (_rightPtr != null) children.add(_rightPtr);

		return children; 
	}
}